In a telephony network, a first user associated with a first user terminal places a call to a second user associated with a second user terminal. The telephony network may be a traditional public switched telephone network (PSTN) or a packet-switched network, such as the Internet. In the case of a packed-switched network, the call may be a voice only call, known as a Voice over Internet Protocol (VoIP) call or the call may be a multi-media call, for example also including video transmission.
Each user terminal is typically associated with identifier data, such as a telephone number conforming to the ITU-T E.164 recommendation. In the PSTN, telephone numbers are used as both primary identifiers and as routing labels for switching circuits to establish a telephone call.
For example, in a phone number “1 212 505 3456”, the first digit ‘1’ identifies the destination country (in this case, the USA), the next three digits ‘212’ identify the area code (New York City), the next three digits ‘505’ identify an exchange, which is generally a block of phone lines serviced by a particular central office, and the remaining four digits ‘3456’ identify a particular phone line served by that central office. If someone in San Francisco dials this phone number, the phone switch to which that person's terminal is connected does not immediately connect directly to the destination phone line. Rather, it selects a trunk line based on the area code ‘212’ and policy known to the switch, generally selected via a table in the switch or via a lookup in a routing database. This trunk might connect directly to a peer switch in New York, or it might connect to a transit switch that serves to aggregate traffic leaving San Francisco. In this latter case, several such trunk-selection operations might occur, with several switches being traversed, before the call reaches New York. Further such lookup operations connect the call to the called party's central office, which selects a physical copper wire pair to activate, thereby ringing the called party's phone.
For Internet telephony, the circuit-establishment operation of a PSTN is replaced by use of a packet-switched Internet Protocol (IP) network, such as the Internet itself, to convey the telephone call between the two parties. IP networks do not natively use phone numbers. Instead, they use IP addresses, which are 32 (IPv4, specified by RFC 791) or 128 (IPv6, specified by RFC 2460) binary digit strings.
In a typical Internet telephony scenario, a user places a call to a destination telephone number. The Internet telephony terminal connects to a destination IP address (possibly through a series of intermediate IP addresses before reaching that destination) and establishes the phone call. One or more gateway devices that adapt between VoIP and circuit-switched telephony devices may be also be traversed in the process. To route a call it is necessary to evaluate which IP address, or sequence of IP addresses, should be employed to reach a destination. In practice, several such determinations can be made, possibly once at each intermediate device.
Since telephony users typically associate other users with E.164 format telephone numbers and do not associate other users with IP addresses, it is necessary for an Internet telephony service to be able to translate an E.164 format number to an IP address associated with a called party. To address this, ENUM (specified by RFC 3761) is used. ENUM is the Electronic or E.164 Number Mapping standard used to determine Internet communications servers for servicing a given telephone number. ENUM uses a simple lookup in the Domain Name System (DNS) to translate a telephone number into a Uniform Resource Identifier (URI) or IP address that can be used for packet-switched network communications.
The DNS (specified by RFC 1035) is a naming system for computers and other resources associated with the Internet. The DNS translates domain names, which are meaningful to humans, into the numerical identifies which make up the IP address of the node. For example, with the DNS, hostnames such as “www.uspto.gov” are translated using a distributed database into IP addresses (like “151.207.245.67” for www.uspto.gov).
A URI is a string of characters used to identify a name of a resource on the Internet. One form of URI is a Uniform Resource Locator (URL) that specifies where an identified resource is available and the mechanism for retrieving it. An example of a URL used by the World Wide Web is “http://www.uspto.gov” and for email addresses is “usptoinfo@uspto.gov”. With these sort of identifiers, an application (a web browser or email server) typically uses the DNS to convert the identifier into an IP address.
A further consideration in routing of Internet telephony calls is the possibility that the destination for a particular call may be either on an IP network or it may be on the PSTN. If the called party is on the PSTN then access from the IP network to the PSTN is achieved through a gateway, which converts packet-switched VoIP to circuit-switched conventional telephony.
While ENUM provides a basic lookup mechanism for translating telephone numbers to IP addresses, it fails to address a fundamental distinction between the common deployments of Internet Telephony and other Internet applications. Most Internet applications use connection routing entirely at the IP address layer. In this approach, each IP switching element (called a “router”) examines each received packet, examines its IP address, and forwards it towards a destination based on comparing that address with a routing table. This works very well for network traffic that is not particularly delay-sensitive. However, VoIP applications tend to be delay sensitive. For example, if Alice is talking to Bob, and a congested router delays the voice stream from Alice, Bob will hear the problem, either as a skip in the speech, a burst of noise, or some other anomaly. This scenario is addressed by using Quality of Service (QoS), which is a resource reservation control mechanism for providing priority to different applications in a packet-based network, to guarantee a certain level of performance to a data flow. Consequently, Internet telephony providers in practice establish preferred network links between each other, along with specialized peering agreements (contacts) that govern the use of these links. Such peering agreements are also used to establish service level contracts for gateway services used to convert calls from IP to switched PSTN services. Typically, when a call is originated on IP, the originating service provider must select from a range of possible peers to terminate that call by gatewaying it back to the PSTN. The ordered set of IP addresses to be traversed to place a call to a destination terminal is known as the route vector.
In summary, when establishing the route vector to route a call originating from an Internet telephony terminal where the called party is identified by a telephone number, operational and commercial constraints require making routing decisions based on other factors in addition to simple “shortest path” routing. To dynamically select a path across a network, decisions are generally based on a wide range of factors, including current network load, measured latency and loss, contractual relationships between telephony service providers, level of service contract priorities, and other factors. These decision-influencing factors and the rules that determine how they apply to the routing of calls are collectively termed “policy”.
In practice, telephony service providers accumulate large databases of policy information relating to the routing of telephone calls. Such databases, along with the mechanisms needed to query the databases from a telephone call routing point, are collectively termed a “registry”. Registries must process many call routing requests in a short period of time, and in general are performance-constrained, thereby impacting the efficiency of the service providers entire system.
For example, two service providers may have a peering agreement that specifies a first fixed rate for an initial number of call-minutes per month, and a second higher fixed rate for additional minutes. To make a call routing decision between this peer and another possible peer not only are the destination addresses needed, but also the terms of the contracts, the number of minutes already used this month and comparable information about other possible peers. All this information should be delivered as quickly as possible to a server that is making a routing decision.
This invention provides a data structuring and access mechanisms to allow routing of phone calls using telephone numbers or telephone number prefixes in accordance with both shortest-path routing and supporting peering policy.